package com.shiguiwu.springmybatis.algorithm.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: 二分查找
 * todo 针对的是有序数据
 * @author: stone
 * @date: Created by 2021/4/8 22:49
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.search
 */
public class BinarySearch extends AbstractSearch implements Search {

    public BinarySearch(int[] arrays) {
        super(arrays);
    }

    @Override
    public int search(int value) {
        return this.binarySearch(0, arrays.length - 1, value);
    }

    @Override
    public int[] searchArrays(int value) {
        return binarySearchArrays(0, arrays.length - 1, value);
    }


    private int binarySearch(int left, int right, int value) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (arrays[mid] > value) {
            return binarySearch(left, mid - 1, value);
        } else if (arrays[mid] < value) {
            return binarySearch(mid + 1, right, value);
        } else {

            return mid;
        }

    }

    private int[] binarySearchArrays(int left, int right, int value) {
        if (left > right) {
            return new int[0];
        }
        int mid = (left + right) / 2;
        if (arrays[mid] > value) {
            return binarySearchArrays(left, mid, value);
        } else if (arrays[mid] < value) {
            return binarySearchArrays(mid + 1, right, value);
        } else {
            List<Integer> list = new ArrayList<>();
            list.add(mid);
            int temp = mid - 1;
            while (temp >= left && arrays[temp] == value) {
                list.add(temp);
                temp--;
            }
            temp = mid + 1;
            while (temp <= right && arrays[temp] == value) {
                list.add(temp);
                temp++;
            }
            int[] arr = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                arr[i] = list.get(i);
            }
            return arr;
        }

    }


}
